package list

import (
	"errors"
	"fmt"
	"math"
	"reflect"
	"strings"
)

var (
	ErrNilList = errors.New("cannot use nil list")
)

type linkedList struct {
	size    int
	header  *node
	trailer *node
}

func newEmptyLinkedList() *linkedList {
	header := newNode()
	trailer := newNode()
	header.next = trailer
	trailer.prev = header
	return &linkedList{
		size:    0,
		header:  header,
		trailer: trailer,
	}
}

// Len returns the length.
func (l *linkedList) Len() int {
	return l.size
}

// Get returns the `index`-th element.
func (l *linkedList) Get(index int) (interface{}, error) {
	n, err := l.find(index)
	return n.val, err
}

// Set sets the `index`-th element with `val`.
func (l *linkedList) Set(index int, val interface{}) error {
	n, err := l.find(index)
	if err != nil {
		return err
	}
	n.val = val
	return nil
}

// Append add an element with `val` as the last element.
func (l *linkedList) Append(val interface{}) {
	n := newNode(val)
	last := l.trailer.prev
	n.insertBetween(last, l.trailer)
	l.size++
}

// Insert inserts element with val as index-th, and the original index-th element will be move backward.
func (l *linkedList) Insert(index int, val interface{}) error {
	if l == nil {
		return ErrNilList
	}
	if index == l.Len() {
		l.Append(val)
		return nil
	}
	n := newNode(val)
	next, err := l.find(index)
	if err != nil {
		return err
	}
	prev := next.prev
	n.insertBetween(prev, next)
	l.size++
	return nil
}

// Remove removes the index-th element.
func (l *linkedList) Remove(index int) (interface{}, error) {
	n, err := l.find(index)
	if err != nil {
		return nil, err
	}
	l.size--
	return n.disconnect(), nil
}

// RemoveLast removes last element.
func (l *linkedList) RemoveLast() interface{} {
	l.size--
	return l.trailer.prev.disconnect()
}

// RemoveValued removes `count` elements with `val` from left to right.
func (l *linkedList) RemoveValued(val interface{}, count ...int) int {
	var cnt = math.MaxInt64
	oldLen := l.size
	if len(count) > 0 {
		cnt = count[0]
	}
	n := l.header.next
	for cnt != 0 && n != l.trailer {
		next := n.next
		if reflect.DeepEqual(n.val, val) {
			n.disconnect()
			l.size--
			cnt--
		}
		n = next
	}
	return oldLen - l.size
}

// ReverseRemoveValued removes `count` elements with `val` from right to left.
func (l *linkedList) ReverseRemoveValued(val interface{}, count ...int) int {
	var cnt = math.MaxInt64
	oldLen := l.size
	if len(count) > 0 {
		cnt = count[0]
	}
	n := l.trailer.prev
	for cnt != 0 && n != l.trailer {
		prev := n.prev
		if n.val == val {
			n.disconnect()
			l.size--
			cnt--
		}
		n = prev
	}
	return oldLen - l.size
}

// ForEach consumes element one by one with `consumer` until all elements run out or any consumer returns false;
//         returns whether all consumers return true.
func (l *linkedList) ForEach(consumer Consumer) bool {
	n := l.header.next
	index := 0
	for n != l.trailer {
		if !consumer(index, n.val) {
			return false
		}
		n = n.next
		index++
	}
	return true
}

// Contains judge if contains element with `val`.
func (l *linkedList) Contains(val interface{}) bool {
	notFound := l.ForEach(func(i int, v interface{}) bool {
		return v != val
	})
	return !notFound
}

// Range returns slice of element value with index `from` start to `end`.
func (l *linkedList) Range(start, end int) []interface{} {
	res := make([]interface{}, 0, end-start)
	var index = 0
	n := l.header.next
	appendFlag := false
	for n != l.trailer {
		if index == start {
			appendFlag = true
		}
		if index == end {
			appendFlag = false
		}
		if appendFlag {
			res = append(res, n.val)
		}
		index++
		n = n.next
	}
	return res
}

// String returns list's string representation formatted like [1, 2, 3, 4, 5].
func (l *linkedList) String() string {
	builder := strings.Builder{}
	builder.WriteString("[")
	l.ForEach(func(i int, val interface{}) bool {
		s := fmt.Sprint(val)
		if i != 0 {
			builder.WriteString(", ")
		}
		builder.WriteString(s)
		return true
	})
	builder.WriteString("]")
	return builder.String()
}

func (l *linkedList) find(index int) (*node, error) {
	if index >= l.size {
		return l.trailer, errors.New("[List] index out of bound")
	}
	n := l.header.next
	for index != 0 && n != l.trailer {
		n = n.next
		index--
	}
	return n, nil
}

type node struct {
	val  interface{}
	prev *node
	next *node
}

func newNode(val ...interface{}) *node {
	var v interface{} = struct{}{}
	if len(val) > 0 {
		v = val[0]
	}
	return &node{
		val:  v,
		prev: nil,
		next: nil,
	}
}

func (n *node) insertBetween(prev, next *node) {
	n.prev = prev
	n.next = next
	prev.next = n
	next.prev = n
}

func (n *node) disconnect() interface{} {
	if n.prev == nil || n.next == nil {
		panic("[List] forbidden to remove header or trailer")
	}
	n.prev.next = n.next
	n.next.prev = n.prev
	return n.val
}
